There has been explosive growth in Internet traffic due to the increased number of Internet users, various service demands from those users, the implementation of new services, such as voice-over-IP (VoIP) or streaming applications, and the development of mobile Internet. Conventional routers, which act as relaying nodes connected to sub-networks or other routers, have accomplished their roles well, in situations in which the time required to process packets, determine their destinations, and forward the packets to the destinations is usually smaller than the transmission time on network paths. More recently, however, the packet transmission capabilities of high-bandwidth network paths and the increases in Internet traffic have combined to outpace the processing capacities of conventional routers.
This has led to the development of massively parallel, distributed architecture routers. A distributed architecture router typically comprises a large number of routing nodes that are coupled to each other via a plurality of switch fabric modules and an optional crossbar switch. Each routing node has its own routing (or forwarding) table for forwarding data packets via other routing nodes to a destination address.
Traditionally, a single processor is used to forward all packets in a router or switch. Even in routers with multiple forwarding table lookup threads, these threads are under control of a single processor and use a single forwarding table. This is true even in routers that use multiple routing nodes, since a single forwarding table and control processor are used in each node.
In order to achieve higher throughput speeds, some routers may use two forwarding tables. One forwarding table is used to perform searches while the second table is updated with new routes. After a defined time period, the router switches from one table to the other. However, using a single forwarding processor creates problems in building and switching to new forwarding tables without impeding traffic flow. Some conventional systems simply drop packets during table changes.
Two methods may be used to avoid dropping packets. In one method, the router buffers data packets and forwards them after the switch. The other method uses two tables, where one table is written while the other table is read for forwarding lookups. The workload on the control plane processor in building and writing the forwarding tables is significant.
However, it is not possible to meet the 10 Gigabit per second (Gbps) forwarding speeds of newer networks using traditional router architectures. This problem is aggravated by the longer searches needed to support the larger address space of IPv6. Memory bandwidth and processing speed limitations prevent support of high data rates and deep trie tree searches. Dropping packets is unacceptable, especially with high data rates and large tables, where vast quantities of packets would be dropped during the switch. Buffering data packets is impractical due to the extremely large quantities of fast memory that would be required by the high data rate. Even if two tables are used, the traditional method of building and/or writing the tables for each processor puts a heavy load on the control plane processor, due to the complexity of the distribution of the forwarding process among network processors, microengines, and threads.
The Applicants disclosed an apparatus and a related method for maintaining high-speed lookup tables in U.S. patent application Ser. No. 10/860,691, entitled “Apparatus and Method for Maintaining High-Speed Forwarding Tables in a Massively Parallel Router”, and filed on Jun. 3, 2004. The subject matter disclosed in U.S. patent application Ser. No. 10/860,691 is hereby incorporated by reference into the present disclosure as if fully set forth herein. The router disclosed in U.S. patent application Ser. No. 10/860,691 implemented a plurality of routing nodes, wherein each routing node used an inbound network processor to forward received data packets from external interfaces to a switch fabric and an outbound network processor to forward received data packets from the switch fabric to the external interface.
The inbound and outbound network processors in U.S. patent application Ser. No. 10/860,691 used a shared search table or forwarding table to forward data packets. The shared search table was implemented in a field programmable gate array (FPGA) complex and used a vector table to index into a trie tree search table. The shared search table was split into an upper memory bank and a lower memory bank. The microengines of the inbound and outbound network processors used one memory bank to perform lookup operations while a control plane processor of the inbound network processor updated the other memory bank with route information. The microengines would then be periodically switched over to the updated memory bank using a polling table swap mechanism.
One disadvantages of the polling table swap mechanism discussed in U.S. patent application Ser. No. 10/860,691 is that the base address of the vector tables must be at a fixed memory location. Another disadvantage is that the reader thread in each network processor must maintain state information on the FPGA state register. Another disadvantage is that both the inbound and outbound network processors must contend for access to the FPGA state register.
Therefore, there is a need in the art for an improved high-speed router that is capable of switching between split halves of a search table without using the polling table method described above. In particular, there is a need in the art for a high-speed router in which the vector tables used to index into a trie tree search table are not required to be a fixed location.